\documentclass[a4paper,twocolumn,10pt]{jceee-kyushu-english}

% For figure environment
\usepackage{graphicx}
% For wrap environment 
\usepackage{ascmac}
\usepackage{paralist}

%\renewcommand{\baselinestretch}{0.85}% <- You can adjust spacing between lines.

\title{
A study on detecting and removing raindrops for videos
%
% If title uses only one line, please make the second line blank as follows: 
% Sample Paper for Asian Sessions \\
% ~ 
}

\author{
Joffrey DIEBOLD$^{*}$, Yuta NAKAHATA$^{**}$, Takuya NAKAGAWA$^{**}$, Hua-An ZHAO$^{**}$ 
\\
}

\affiliation{
(*Department of Computer Science, \textsc{Enseirb-Matmeca}, Bordeaux University)\\
(**Department of Computer Science and Electrical Engineering, Kumamoto University)\\
}

%Email address is not mandatory. If you don't want to present the authors' 
%email addresses, please leave the tilde(~) below so that empty line appears. 
%If you want to present the authors' email addresses, please delete the tilde 
%and write your email addresses. 
\emailaddress{
~ jdiebold@enseirb-matmeca.fr, \{nakahata, nakagawa\}@st.cs.kumamoto-u.ac.jp, cho@cs.kumamoto-u.ac.jp
%\{author1, author3\}@dept1.abc-u.ac.jp, author2@dept2.abc-u.ac.jp, 
%author4@div.def.com
}
\begin{document}
\maketitle

\vspace*{1em}

\section{Introduction}
In this paper, tracks are given about ways to detect and remove rain in videos. This seems quite challenging to the extent that raindrops are randomly and uniformly distributed in a frame. However the flow resulting from the raindrops, their physical and chromatic properties, make it possible to differenciate them.
%

\section{Detection}

The detection of raindrops in a video can be executed by applying a combination of Lucas-Kanade (LK) method and of Gaussian background mixture model (GBMM) with some properties of a raindrops mentioned as follows.

\subsection{Lucas-Kanade method}

Lucas-Kanade method computes the optical flow of objects on a footage, and the result is two matrices of the same size of a frame. The first contains the horizontal velocity of each pixel and the second one contains their vertical velocity. These data are useful to determine the speed and the angle of pixels during the video.

\subsection{Gaussian background mixture model}

Gaussian background substract (GBS) is a method used to detect foreground by using a background learning model. Is is especially efficient in a static camera footage, as the background remains strictly the same. GBMM is a particular case of GBS which can be used combined to LK method in order to detect rain.

\subsection{OFBM}

Background removal or foreground detection is the basis of detection of raindrops, the result of foreground detection will directly decide the performance of detections.
Because raindrops movement is wide-area, it is necessary to detect the change on every pixels, so LK optical flow is the best choice. However, optical flow methods are very sensitive to illumination change, it is difficult to find a proper threshold to detect foreground and background by LK method. Therefore, we present a new approach by combining LK optical flow with GBS method to get an optimal foreground, called optical flow and background model (OFBM) \cite{cho} (figure \ref{ofbm}).

\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{ofbm.eps}
\caption{Outline of OFBM for background removal}
\label{ofbm}
\end{figure}


\subsection{Properties of a raindrop}

\begin{compactitem}
\item The \textbf{speed} of raindrops is high enough to be noticed. As mentionned above, the LK-method enables to obtain it. Then a speed limit can be set to select candidate pixels for rain. Above this limit, the next parameter can be computed.

\item In a rainy scene which is not disturbed by too much wind, all the raindrops share nearly the same falling \textbf{angle}. By observing briefly the video, an estimated angle can be determined. Then the possible errors will be corrected with a small "epsilon" angle. Figure \ref{angle} indicates which angle is considered.

\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{angle.eps}
\caption{Falling angle of raindrops}
\label{angle}
\end{figure}

The value of the angle is obtained by the equation \ref{angle-eq}.

\begin{equation}
\theta = \arctan{|\frac{V_y}{V_x}|}
\label{angle-eq}
\end{equation}

Figure \ref{angle-speed} demonstrates the link between the angle and the speed vector of a raindrop pixels.

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{angle2.eps}
\caption{Angle and speed of raindrops}
\label{angle-speed}
\end{figure}

\item The \textbf{brightness} of a raindrop is often much higher than the one of the background. A simple criterium is to compute for every frame $i_t = \frac{i_{max} + i_{min}}{2}$, where $i_{max}$ and $i_{min}$ are respectively the pixel with the maximal and minimal intensity.
\item The \textbf{size} of a raindrop is most of the time inferior to 1 mm, which is a criterium \cite{garg-nayar}.
\end{compactitem}

\subsection{Results}

Detection has been tested on some differents videos, the camera being static. The results have been satisfying when combining LK method with the angle and the speed criteria (figure \ref{lk-angle}) or when combining OFBM method with the angle and the speed criteria (figure \ref{ofbm-angle}).

\begin{figure}[h]
\begin{center}
\scalebox{0.5}[0.5]{\includegraphics{lk-original.eps}}
\scalebox{0.5}[0.5]{\includegraphics{lk-result.eps}}
\caption{LK + angle + speed criteria}
\label{lk-angle}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
\scalebox{0.5}[0.5]{\includegraphics{ofbm-original.eps}}
\scalebox{0.5}[0.5]{\includegraphics{ofbm-result.eps}}
\caption{OFBM method + angle + speed criteria}
\label{ofbm-angle}
\end{center}
\end{figure}


%------------------------------------------------

\section{Removal}

Once raindrops pixels have been selected, they have to be removed from the video, \textit{ie} they have to look like non-rain pixels. Three main methods can be used: the average method, an interpolation or a least square approximation.

\subsection{Average method}

The average method consists in replacing a raindrop pixel intensity (successively the red, green and blue values) by the average of the same pixel intensities in the previous and the next frame. More formally, $i_n = \frac{i_{n-1} + i_{n+1}}{2}$ has to replace the old $i_n$ value, where $i_n$ is the intensity of a given pixel in the $n^{th}$ frame.\\
The advantage of this method is its simplicity and the complexity of the algorithm: for the computation of one pixel's intensity, it is constant. For the whole video the complexity is $O(N \times P)$, where $N$ is the number of frames in the video and $P$ is the number of pixels in a frame.\\
However, it is far from being satisfying. Indeed, sometimes in the previous or in the next frame, the considered pixel still belongs to a raindrop. That leads to a mistake which can spread along the algorithm execution.

\subsection{Interpolation}

An interpolation can be done with Lagrange's polynome formula which is given by equation \ref{lagrange}.
\begin{equation}
L(x) = \sum_{i=0}^N y_i \prod_{j=0, j\neq i}^N \frac{x-x_j}{x_i-x_j}
\label{lagrange}
\end{equation}

$N$ is the number of frames, $x_i$ is the frame number in which the pixel appears, and $yi$ is the intensity of the pixel. The interpolation has to be done with pixels that do not belong to a raindrop. This method is more precise than the previous one but is costly in terms of time resources. The complexity of the computation of one pixel is quadratic, which means the complexity of the whole algorithm is $O(N^3 \times P)$.

\subsection{Least mean square approximation}

This method is probably the best compromise. It consists in considering pixels $(x_i,y_i)$ (with the same notations than the last paragraph) that are not part of a raindrop, and finding the curve which fits the computed values the best. Formally, a function $f(x, \beta)$ has to be found, where $\beta$ is a vector. The absolute value of the residual $r_i = y_i - f(x_i, \beta_i)$ has to be minimised. The function being found, the intensities of the raindrop pixels can be replaced.\\
The main advantage of this method relies on being able to choose the degree of the curve. Let $C$ be the dimension of $\beta$. The degree $d$ of the curve satisfies $C=d+1$. The complexity of this method is, for one pixel, $O(N \times C^2)$, which is better than Lagrange method. Especially, if a simple linear regression is done (\textit{ie} $C=2$), it can be said that the complexity is $O(N)$. Thus the total algorithm complexity with this method is $O(N^2 \times P)$.

%------------------------------------------------

\section{Conclusion}

Different methods of detecting and removing rains have been explained. Some are clearly more determining than others, but it should be kept in mind that a large range of video conditions may alter the efficiency of the methods. Thus, rain intensity may alter the detection, as well as the global brightness of the video footage.

\section*{Acknowledgement}
We would like to thank those who helped us to realise this paper, especially Alexia MENAND and Jean-Baptiste BERNARD, department of Computer Science, \textsc{Enseirb-Matmeca}, Bordeaux University.

\begin{thebibliography}{99}
\bibitem{garg-nayar} Kshiti Garg, Shree K. Nayar, "Detection and removal of Rain from Videos", Proc. of IEEE CVPR 2004.
\bibitem{cho} Wei Li, Xiaojuan Wu and Hua-An Zhao, "New Techniques of Foreground Detection, Segmentation and Density Estimation for Crowded Objects Motion Analysis," Journal of Information Processing Vol.19, pp.190–200, 2011.
\end{thebibliography}

\end{document}
